1. Field of the Invention
The present invention relates to systems and methods for decoding data in communication or data storage systems. In particular, the present invention relates to systems and methods for early detection of a correctly decoded codeword from a layered low density parity check (LDPC) decoder.
2. Description of Related Art
In communication and data storage systems, information bearing signals received by receivers or controllers may be corrupted by noise, interference, or other types of disturbances. To improve the probability that the information is correctly reconstructed, error correction codes (ECC) are frequently used to introduce redundancy bits or parity bits in the data bearing the information. LDPC codes belong to a category of ECC called linear block codes. LDPC codes are characterized by parity check matrices that are very sparse, meaning a low density of non-zero elements. An LDPC decoder may iteratively determine the most likely information-bearing codeword corresponding to a received vector. LDPC decoding can be realized by sum-product or min-sum decoding algorithms or their variants. Irrespective of specific decoding algorithm, given an LDPC code defined by an m×n parity check matrix. LDPC decoding can be represented by an iterative message update and passing process between m check (or constraint) nodes in one set and n bit (or message) nodes in the other set. Different message update computation rules and/or different message passing (or exchange) scheduling strategies lead to different LDPC decoding algorithms. To verify a decoded codeword, the LDPC decoder may perform a matrix multiplication of a vector of hard decisions with the parity check matrix of the LDPC code in a parity check operation. A valid codeword is declared when the result of the matrix multiplication generates a zero vector. For example, in an LDPC code of block length n having (n−m) information bits and m parity bits (i.e., code rate is (n−m)/n), the parity check matrix may be an m×n binary matrix. Matrix multiplication of the m×n parity check matrix with n×1 hard decisions of a received vector generates m check nodes or parity nodes. In layered LDPC decoding, each row of the m×n parity check matrix is called a layer. Each layer has a check node, and the exclusive-or of all the hard decisions having elements of one in a layer of the matrix (i.e. bit nodes), generates the syndrome for that layer. The code word is correctly decoded when the syndromes for all the layers are zero.
In a conventional layered LDPC decoder, the generation of hard decisions may proceed in layers. The syndrome for a current layer may be updated when the hard decisions for the bit nodes of the layer are received. To update the syndromes for all the layers it may take m clock cycles for the layered LDPC decoder to run through all m layers. When the hard decision of any bit node changes during layered decoding, it may take another m clock cycles to verify that the syndromes for all the layers are zero. This approach increases decoding latency and decreases decoding throughput.
Furthermore, because a conventional layered LDPC decoder constantly updates the hard decisions, layered decoding may need to be halted during the parity check operation, which would degrade the decoding throughput even further. One way to avoid halting the decoding process during the parity check calculation is to have two sets of hard decision memories. Run-time parity check and hard decision updates may proceed in parallel by alternatively operating between the two memories. However, the extra copy of hard decision memory increases cost, area, and power consumption. There is also no guarantee that the parity check operation will terminate as soon as all the hard decisions are generated because the exit time may still depend upon when the correct decoded data enters the hard decision memory. In the worst case it may still take m clock cycles after the last hard decision is generated to finish the syndrome calculation and for the parity check operation to indicate the completion of decoding. As such, it is desirable to have a minimal, fixed exit delay from a run-time parity check of a layered LDPC decoder while minimizing any increase in cost, area, and power.